The present invention is directed to communications networking. It is directed particularly to providing routing for private wide-area networks.
1. Private Wide-Area Networks
An enterprise that has many sites can build a private wide-area network by placing routers at each site and using leased lines to interconnect them. A router that has a wide-area connection to another router may be called a xe2x80x9cbackbone router.xe2x80x9d The xe2x80x9cbackbone networkxe2x80x9d is the set of backbone routers and their interconnections.
If every backbone router is connected to every other backbone router, the backbone network is said to be xe2x80x9cfully meshed.xe2x80x9d In a fully meshed backbone network, data that travel from one site to another go through the backbone router at an origin site (xe2x80x9cingress routerxe2x80x9d), travel over the leased line to the backbone router at the target site (xe2x80x9cegress routerxe2x80x9d), and then enter the target site. More commonly, though, the backbone network is not fully meshed; a router is connected to only a small number of others (three or four). In such a sparse topology, the ingress and egress routers may not be directly connected. In this case, data may have to pass through several additional, xe2x80x9ctransitxe2x80x9d routers on the way from ingress to egress.
In a private network like this, the design and operation of the backbone network is the responsibility of the enterprise. A routing algorithm must run in the backbone routers, enabling them to tell each other the addresses of the destinations to which they can respectively afford access.
It is worth noting that a leased line is not actually a piece of wire going from one site to another. It is really a circuit through some circuit-switching network. But this is of no import to the enterprise network manager, to whom those circuits can be considered simple unstructured pipes. Conversely, although the telephone network itself requires considerable management, the telephone-network managers do not need to know anything about the enterprise backbone network; to them, the telephone network just provides point-to-point connections. They do not need to know what role these connections might be playing in an enterprise data network.
We may say that the enterprise network is xe2x80x9coverlaidxe2x80x9d on top of the telephone network. The enterprise network can be called the xe2x80x9chigher layerxe2x80x9d network, the telephone network the xe2x80x9clower layerxe2x80x9d network. Both networks exist, but each is transparent to the other. The enterprise""s backbone routers exchange routing information with each other, but the telephone switches do not store or process that routing information. That is, backbone routers are xe2x80x9crouting peersxe2x80x9d of each other, but they are not routing peers of the telephone switches. This way of building a higher-layer network on top of a lower-layer network is called the xe2x80x9coverlay model.xe2x80x9d
2. Virtual Private Networks
Wide-area enterprise networks are now more likely to be built on top of frame-relay and ATM networks than on top of circuit-switched (telephone) networks. Whereas a telephone network really provides circuits between backbone routers, a frame-relay or ATM network provides xe2x80x9cvirtual circuitsxe2x80x9d between backbone routers. But this changes nothing as far as the enterprise""s routing task is concerned; the overlay model still applies even though the lower-layer network is now a frame-relay or ATM network rather than a circuit-switched one, i.e., even though virtual rather than fixed circuits make the point-to-point connections between backbone routers. The two networks are still transparent to each other. The enterprise network manager still has a wide-area backbone to design and operate. However, because the circuits are xe2x80x9cvirtual,xe2x80x9d this is usually called a xe2x80x9cvirtual private networkxe2x80x9d (VPN) instead of a xe2x80x9cprivate network.xe2x80x9d
Since the two networks are transparent to each other in the overlay model, that model is distinguished by the fact that the enterprise""s backbone routers do not share with the (service provider""s) frame-relay or ATM switches the routing information that they must share with each other. This causes inefficiency when the enterprise""s backbone routers are not fully meshed. In such networks, some packets go from the ingress router through one or more transit routers before they reach the egress router. At each one of these xe2x80x9chops,xe2x80x9d the packet leaves the frame-relay or ATM network and then enters it again. This is sub-optimalxe2x80x94there is little value in having a packet go in and out of the frame-relay or ATM network multiple times.
This problem can be avoided by making the enterprise backbone fully meshed, but that causes problems of its own. The number of virtual circuits the enterprise has to pay the service provider for to make the network fully meshed grows as the square of the number of backbone routers. Apart from the cost, routing algorithms tend to scale poorly as the number of direct connections between routers grows. This causes additional problems.
The overlay model also tends to result in extra traffic when multicast is in use. It is usually impractical or undesirable for the xe2x80x9clower layerxe2x80x9d network to do the necessary packet replication, so all packet replication must be done in the xe2x80x9chigher layerxe2x80x9d network, even if a number of replicated packets must then follow the same xe2x80x9clower layerxe2x80x9d path up to a point.
3. The Peer Model
Since these considerations all impose upon the resources of an enterprise for which communications is not necessarily a core competence, a service provider (xe2x80x9cSPxe2x80x9d) can afford its customers greater value if it absorbs the task of designing and operating the backbone. More specifically, the SP should so organize and operate the backbone that, from the point of view of a particular site administrator, every enterprise network address not located at a given site is reachable through the SP""s backbone network. How the SP""s backbone decides to route the traffic is the SP""s concern, not that of the customer enterprise. So the customer enterprise does not really need to maintain a backbone router at each site; it just needs a router that attaches to one of the SP""s backbone routers. As will become apparent, providing such an organization involves abandoning the overlay model for a different model. The new model will be called the xe2x80x9cpeer modelxe2x80x9d for reasons that will be set forth below.
Terminology:
C-network: the enterprise network, consisting of C-routers, which are maintained and operated by the enterprise.
P-network: the SP network, consisting of P-routers, which the SP maintains and operates.
CE-router: an xe2x80x9cedge routerxe2x80x9d in the C-network, i.e., a C-router that attaches directly to a P-router and is a routing peer of the P-router.
PE-router: an xe2x80x9cedge routerxe2x80x9d in the P-network, i.e., a P-router that attaches directly to a C-router and is a routing peer of the C-router.
If a P-router is not a PE-router, i.e., not an edge router, it is a transit router. The concept of edge and transit routers is relative to specific VPNs. If a given one of the SP""s routers receives a given VPN""s traffic from and forwards it to only others of the SP""s routers, the given router is a transit router vis-à-vis the given VPN. Yet that same router may receive another VPN""s traffic from and/or forward it to one of that other VPN""s edge routers, in which case the given SP router is an edge router from the other VPN""s point of view.
In the conventional peer model, where xe2x80x9cvirtual routersxe2x80x9d (i.e., one instance of the routing algorithm per VPN) are used, all C-routers within the same VPN are routing peers of each other. But two C-routers will be routing adjacencies of each other only if they are at the same site. Each site has at least one CE router, each of which is directly attached to at least one PE router, which is its routing peer. Since CE routers do not exchange routing information with each other, there is no virtual backbone for the enterprise to manage, and there is never any need for data to travel through transit CE routers. Data go from the ingress CE router through a sequence of P-routers to the egress CE router. So the resultant routing is optimal. These clear customer benefits have led certain SPs to adopt the peer model.
The conventional peer-model approach also enables the SP to solve certain problems that arise from using a common backbone network for more than one client. One of these is address duplication. Although there is an international assigned-number authority from which unique addresses can be obtained, many enterprise networks simply assign sign their private-network addresses themselves. So their addresses are unique only within the particular enterprise: they may duplicate addresses that another customer enterprise uses. An SP trying to use, say, an Internet-Protocol (xe2x80x9cIPxe2x80x9d) backbone as the backbone for different enterprise networks having overlapping address spaces needs to provide its P-routers with a way of identifying and selecting a route to the one of potentially many same-address destinations to which it should forward a packet.
So the SP makes use of a xe2x80x9cvirtual router.xe2x80x9d When a PE router receives a packet received from a CE router, the PE router xe2x80x9ctagsxe2x80x9d the packet with an indication of the C-network where it originated. It then bases its determination of what router to forward the packet to not only on the packet""s destination address but also on the identity of the originating C-network. At each subsequent hop, the router looks up the packet""s destination address in the forwarding table specific to the C-network that the tag designates.
This also solves another multiple-customer problem, that of the access control. If an enterprise buys network-backbone service from an Internet SP, it wants some assurance that its network receives only packets that originated in its own network. It also wants to be sure that packets originating in its network do not leave the enterprise network by accident. Of course, two enterprises might want to be able to communicate directly, or to communicate over the Internet. But they want such communication to occur only through xe2x80x9cfirewalls.xe2x80x9d By using the virtual router, the SP solves this problem, too.
The above-identified parent patent applicaton describes a way for an SP to provide its customers the peer model""s advantages at costs considerably lower than those that the conventional virtual-router approach exacts. The present invention can be used to enable such systems to help support the customer network""s security measures. A provider network employing this technique associates internal and external identifiers, which we call xe2x80x9cVPN IDs,xe2x80x9d with a customer network and employs these selectively in forwarding reachability messages relating to customer nodes.
Specifically, a provider edge router linked to a given customer""s edge router in a system that employs the present invention""s teachings will ordinarily relay reachability information concerning customer sites from that router only to provider edge routers similarly linked to other edge routers of the same customer, to which they will in turn forward the reachability information. In doing so, it will include the customer""s internal VPN ID in the message so that the receiving provider router can disambiguate the possibly non-unique IP address that the reachability message specifies. Those other provider edge routers will not forward the information to other outside routers that are not part of the nework of the customer involved. But there is at least one of the same customer""s edge routers from which a reachability message will cause the provider edge router linked to it to relay the reachability information to other provider edge routers and include the customer network""s external VPN ID in doing so. This will typically be a router through which packets entering the customer""s network must pass through a firewall, so it is the one to which traffic from outside that network should be sent.
When a provider edge router then receives from outside that customer network a packet directed to the address whose reachability was advertised with the customer""s external VPN ID, it forwards the toward the provider edge router that attached the external VPN ID to the reachability message that advertised the destination, and that router can send it to the firewall site. In contrast, packets from within the customer network can be sent to through provider edge routers that used the internal VPN ID for reporting the destination""s visibility.